/// @tags: Matrix Recursion
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef unsigned long long ull;

ull const mod = 9223372036854775783;

struct Matrix {
  ull a[4][4];

  Matrix() { memset(a, 0, sizeof(a)); }

  inline Matrix operator*(const Matrix &rhs) const {
    Matrix res;
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j)
        for (int k = 0; k < 4; ++k) {
          res.a[i][j] = res.a[i][j] + static_cast<__int128_t>(a[i][k]) * rhs.a[k][j] % mod;
          if (res.a[i][j] >= mod) res.a[i][j] -= mod;
        }
    return res;
  }

  inline Matrix operator^(ull exp) {
    Matrix res;
    for (int i = 0; i < 4; ++i) res.a[i][i] = 1;
    while (exp) {
      if (exp & 1) res = res * *this;
      *this = *this * *this;
      exp >>= 1;
    }
    return res;
  }
} A, T;

ull n;

template <typename T>
inline T &read(T &x) {
  x = 0;
  int ch = getchar();
  while (!isdigit(ch)) { ch = getchar(); }
  while (isdigit(ch)) {
    x = x * static_cast<__int128_t>(10) % (mod - 1) + (ch ^ '0'), ch = getchar();
    if (x >= mod - 1) x -= mod - 1;
  }
  return x;
}

int main() {
  read(n);
  A.a[0][0] = 1, A.a[0][2] = 2, A.a[0][3] = 1;
  T.a[0][0] = 2, T.a[0][1] = 1;
  T.a[1][0] = 2, T.a[1][1] = 2;
  T.a[2][0] = 3, T.a[2][1] = 1, T.a[2][2] = 2;
  T.a[3][0] = mod - 2, T.a[3][1] = mod - 1, T.a[3][3] = 1;
  cout << (A * (T ^ (n - 1))).a[0][0];
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4967 黑暗打击.in", "r", stdin);
  freopen("P4967 黑暗打击.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
